{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize the Confusion of an Exam"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxConsecutiveAnswers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #考试的最大困扰度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一位老师正在出一场由 <code>n</code>&nbsp;道判断题构成的考试，每道题的答案为 true （用 <code><span style=\"\">'T'</span></code> 表示）或者 false （用 <code>'F'</code>&nbsp;表示）。老师想增加学生对自己做出答案的不确定性，方法是&nbsp;<strong>最大化&nbsp;</strong>有 <strong>连续相同</strong>&nbsp;结果的题数。（也就是连续出现 true 或者连续出现 false）。</p>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>answerKey</code>&nbsp;，其中&nbsp;<code>answerKey[i]</code>&nbsp;是第 <code>i</code>&nbsp;个问题的正确结果。除此以外，还给你一个整数 <code>k</code>&nbsp;，表示你能进行以下操作的最多次数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每次操作中，将问题的正确答案改为&nbsp;<code>'T'</code> 或者&nbsp;<code>'F'</code>&nbsp;（也就是将 <code>answerKey[i]</code> 改为&nbsp;<code>'T'</code>&nbsp;或者&nbsp;<code>'F'</code>&nbsp;）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回在不超过 <code>k</code>&nbsp;次操作的情况下，<strong>最大</strong>&nbsp;连续 <code>'T'</code>&nbsp;或者 <code>'F'</code>&nbsp;的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>answerKey = \"TTFF\", k = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们可以将两个 'F' 都变为 'T' ，得到 answerKey = \"<em><strong>TTTT</strong></em>\" 。\n",
    "总共有四个连续的 'T' 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>answerKey = \"TFFT\", k = 1\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = \"<em><strong>FFF</strong></em>T\" 。\n",
    "或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = \"T<em><strong>FFF</strong></em>\" 。\n",
    "两种情况下，都有三个连续的 'F' 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>answerKey = \"TTFTTFTT\", k = 1\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>我们可以将第一个 'F' 换成 'T' ，得到 answerKey = \"<em><strong>TTTTT</strong></em>FTT\" 。\n",
    "或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = \"TTF<em><strong>TTTTT</strong></em>\" 。\n",
    "两种情况下，都有五个连续的 'T' 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == answerKey.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>answerKey[i]</code>&nbsp;要么是&nbsp;<code>'T'</code> ，要么是&nbsp;<code>'F'</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-the-confusion-of-an-exam](https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-the-confusion-of-an-exam](https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"TTFF\"\\n2', '\"TFFT\"\\n1', '\"TTFTTFTT\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        n1, n2 = 0, 0\n",
    "        if answerKey[l] == 'T':\n",
    "            n1 += 1\n",
    "        else:\n",
    "            n2 += 1\n",
    "        for r in range(1,len(answerKey)):\n",
    "            if answerKey[r] == 'T':\n",
    "                n1 += 1\n",
    "            else:\n",
    "                n2 += 1\n",
    "            if min(n1,n2) > k:\n",
    "                if answerKey[l] == 'T':\n",
    "                    n1 -= 1\n",
    "                else:\n",
    "                    n2 -= 1\n",
    "                l += 1\n",
    "        return r - l + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        # 两种情况：T最长，F最长，取最大值\n",
    "        def cnt(v):\n",
    "            left, res, k0 = 0,0,k\n",
    "            for right,x in enumerate(answerKey):\n",
    "                if x == v: k0 -= 1\n",
    "                while k0 < 0:\n",
    "                    if answerKey[left] == v:\n",
    "                        k0 += 1\n",
    "                    left += 1\n",
    "                res = max(res, right-left+1)\n",
    "            return res\n",
    "        return max(cnt('T'), cnt('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        numT = 0\n",
    "        numF = 0\n",
    "        for right, ch in enumerate(answerKey):\n",
    "            if ch == \"T\":\n",
    "                numT += 1\n",
    "            else :\n",
    "                numF += 1\n",
    "            while min(numF, numT) > k:\n",
    "                if answerKey[left] == \"T\":\n",
    "                    numT -= 1\n",
    "                else:\n",
    "                    numF -= 1\n",
    "                left += 1\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans\n",
    "                    #怎么删计数，如果都为1\n",
    "\n",
    "    #对Right：把ch加入Counter，如果len Counter 小于1，继续右移（更新ans\n",
    "    #对left：当len C等于二时，如果k>0,k-=1，Counter中ch计数删掉，len C仍然为1，left不动，right右移更新ans\n",
    "    #如果k=0，则left左移直到lenC等于1或者lenC为2时最小计数小于等于k：减去left在C中计数，k重置\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        # 最多删除k个T得到最大连续F与最多杀出k个F得到最大连续T比较\n",
    "        def solve(c):\n",
    "            res = 0\n",
    "            l, w = 0, 0\n",
    "            n = len(answerKey)\n",
    "            for i in range(n):\n",
    "                if answerKey[i] == c:\n",
    "                    w += 1\n",
    "                while l <= i and w > k:\n",
    "                    if answerKey[l] == c:\n",
    "                        w -= 1\n",
    "                    l += 1\n",
    "                res = max(res, i - l + 1)\n",
    "            return res\n",
    "        return max(solve('F'), solve('T'))\n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def f(s):\n",
    "            ans = 0\n",
    "            left = 0\n",
    "            sum = 0\n",
    "            for right in range(len(answerKey)):\n",
    "                if answerKey[right] != s:\n",
    "                    sum += 1\n",
    "                if sum > k:\n",
    "                    ans = max(ans, right - left)\n",
    "                while sum > k:\n",
    "                    sum -= int(answerKey[left] != s)\n",
    "                    left += 1\n",
    "            return max(ans, len(answerKey) - left)\n",
    "        return max(f('T'), f('F'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        left = cnt = 0\n",
    "        for right,a in enumerate(answerKey):\n",
    "            if a == 'T':\n",
    "                cnt += 1\n",
    "            while cnt > k:\n",
    "                if answerKey[left] == 'T':\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            ans = max(ans,right-left+1)\n",
    "        res = 0\n",
    "        left = cnt = 0\n",
    "        for right,a in enumerate(answerKey):\n",
    "            if a == 'F':\n",
    "                cnt += 1\n",
    "            while cnt > k:\n",
    "                if answerKey[left] == 'F':\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return max(res,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = left = cnts_t = cnts_f = 0\n",
    "        for right, c in enumerate(answerKey):\n",
    "            cnts_t += c == 'T'\n",
    "            cnts_f += c == 'F'\n",
    "            # 当前区间内的t和f的个数不能都大于k，我们只能变k次\n",
    "            while cnts_t > k and cnts_f > k:\n",
    "                # 超过最大变动次数了，当前指针的区间最左要向右移动\n",
    "                cnts_t -= answerKey[left] == 'T'\n",
    "                cnts_f -= answerKey[left] == 'F'\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   \n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        n = len(answerKey)\n",
    "        def check(answerKey: str, k : int, ch : string) -> int:\n",
    "            ans  = 0\n",
    "            left = 0\n",
    "            sum_ = 0\n",
    "            for right in range(n) :\n",
    "                #print(right)\n",
    "                sum_ += (answerKey[right] != ch) \n",
    "                while sum_ > k :\n",
    "                    sum_ -= answerKey[left] != ch\n",
    "                    left += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "            return ans\n",
    "        return max(check(answerKey, k, \"T\"), check(answerKey, k, \"F\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "\n",
    "        ans = 0 \n",
    "        left = 0\n",
    "        n_t = 0\n",
    "        n_f= 0\n",
    "\n",
    "        for i,n in enumerate(answerKey):\n",
    "            if n == \"T\":\n",
    "                n_t +=1\n",
    "\n",
    "            if n ==\"F\":\n",
    "                n_f += 1\n",
    "\n",
    "            while min(n_f,n_t)>k:\n",
    "                if answerKey[left] == \"T\":\n",
    "                    n_t-=1\n",
    "                if answerKey[left] == \"F\":\n",
    "                    n_f-=1\n",
    "\n",
    "                left+=1\n",
    "\n",
    "            ans = max(ans,i+1-left)\n",
    "\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        num_t = 0\n",
    "        num_f = 0\n",
    "        ans = 0\n",
    "        left = 0\n",
    "\n",
    "        for right,ch in enumerate(answerKey):\n",
    "            if ch == \"T\":\n",
    "                num_t += 1\n",
    "            else:\n",
    "                num_f += 1\n",
    "            while (min(num_f,num_t) > k):\n",
    "                if answerKey[left] == \"T\":\n",
    "                    num_t -= 1\n",
    "                else:\n",
    "                    num_f -= 1\n",
    "                left += 1\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        left, slide_sum = 0, 0\n",
    "        for right, key in enumerate(answerKey):\n",
    "            if key == \"T\": slide_sum += 1\n",
    "            while left < right and slide_sum > k:\n",
    "                if answerKey[left] == \"T\":\n",
    "                    left += 1\n",
    "                    slide_sum -= 1\n",
    "                    break\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        #     print(left, right, ans)\n",
    "        # print()\n",
    "        left, slide_sum = 0, 0\n",
    "        for right, key in enumerate(answerKey):\n",
    "            if key == \"F\": slide_sum += 1\n",
    "            while left < right and slide_sum > k:\n",
    "                if answerKey[left] == \"F\":\n",
    "                    left += 1\n",
    "                    slide_sum -= 1\n",
    "                    break\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "            # print(left, right, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def get_char(ch):\n",
    "            n = len(answerKey)\n",
    "            ans = 0\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            while i < n:\n",
    "                cnt += (answerKey[i] == ch)\n",
    "                while cnt > k:\n",
    "                    cnt -= (answerKey[j] == ch)\n",
    "                    j += 1\n",
    "                ans = max(ans, i - j + 1)\n",
    "                i += 1\n",
    "                \n",
    "            return ans \n",
    "        return max(get_char('T'), get_char('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        num_T=0\n",
    "        num_F=0\n",
    "        ans,left=0,0\n",
    "        for right,ch in enumerate(answerKey):\n",
    "            if ch=='T':\n",
    "                num_T+=1\n",
    "            else:\n",
    "                num_F+=1\n",
    "            while (min(num_T,num_F)>k):#k无法转变滑窗内一样的选项，最小值都比k大\n",
    "                if answerKey[left]=='T':\n",
    "                    num_T-=1\n",
    "                else:\n",
    "                    num_F-=1\n",
    "                left+=1\n",
    "            ans=max(ans,right-left+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        left = right = 0\n",
    "        res = 1\n",
    "        dic = {\"T\":0, \"F\":0}\n",
    "        dic[answerKey[left]] += 1\n",
    "        while right < len(answerKey) - 1:\n",
    "            right += 1\n",
    "            dic[answerKey[right]] += 1\n",
    "            if dic[\"T\"] > k and dic[\"F\"] > k:\n",
    "                dic[answerKey[left]] -= 1\n",
    "                left += 1\n",
    "                if len(answerKey) - left <= res:\n",
    "                    break\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        cnt=0\n",
    "        ans=0\n",
    "        l=0\n",
    "        n=len(answerKey)\n",
    "        for r in range(n):\n",
    "            if answerKey[r]!='T':\n",
    "                cnt+=1\n",
    "                while cnt>k:\n",
    "                    cnt-=answerKey[l]!='T'\n",
    "                    l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        cnt=0\n",
    "        l=0\n",
    "        for r in range(n):\n",
    "            if answerKey[r]!='F':\n",
    "                cnt+=1\n",
    "                while cnt>k:\n",
    "                    cnt-=answerKey[l]!='F'\n",
    "                    l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        n=len(answerKey)\n",
    "        i,j=0,0\n",
    "        tt=Counter()\n",
    "        ans=0\n",
    "        while j<n:\n",
    "            tt[answerKey[j]]+=1\n",
    "            if min(tt['T'],tt['F'])>k:\n",
    "                tt[answerKey[i]]-=1\n",
    "                i+=1\n",
    "            j+=1\n",
    "            ans=max(ans,j-i)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        n = len(answerKey)\n",
    "        res = 0\n",
    "        def count(target):\n",
    "            nonlocal res,k\n",
    "            left,right = 0,0 \n",
    "            window = {}\n",
    "            while right < n:\n",
    "                window[answerKey[right]] = window.get(answerKey[right],0) + 1\n",
    "                while window.get(target,0) > k:\n",
    "                    window[answerKey[left]] -= 1\n",
    "                    left += 1\n",
    "                right += 1\n",
    "                res = max(res,right-left)\n",
    "            return res\n",
    "        return max(count('T'),count('F'))  # 分别尝试改T或F\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def ok(ch):\n",
    "            ans = 0\n",
    "            left = cnt = 0\n",
    "            for right,a in enumerate(answerKey):\n",
    "                if a == ch:\n",
    "                    cnt += 1\n",
    "                while cnt > k:\n",
    "                    if answerKey[left] == ch:\n",
    "                        cnt -= 1\n",
    "                    left += 1\n",
    "                ans = max(ans,right-left+1)\n",
    "            return ans\n",
    "        return max(ok('T'),ok('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def get_char(ch):\n",
    "            n = len(answerKey)\n",
    "            ans = 0\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            while i < n:\n",
    "                cnt += (answerKey[i] == ch)\n",
    "                while cnt > k:\n",
    "                    cnt -= (answerKey[j] == ch)\n",
    "                    j += 1\n",
    "                ans = max(ans, i - j + 1)\n",
    "                i += 1\n",
    "                \n",
    "            return ans \n",
    "        return max(get_char('T'), get_char('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        T = F = left = 0\n",
    "        for c in answerKey:\n",
    "            if c == 'T':\n",
    "                T += 1\n",
    "            else:\n",
    "                F += 1\n",
    "\n",
    "            if T > k and F > k:\n",
    "                if answerKey[left] == 'T':\n",
    "                    T -= 1\n",
    "                else:\n",
    "                    F -= 1\n",
    "                left += 1\n",
    "        return len(answerKey) - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        cnt = Counter()\n",
    "        for right,x in enumerate(answerKey):\n",
    "            cnt[x] += 1\n",
    "            while cnt['T'] > k and cnt['F'] > k:\n",
    "                cnt[answerKey[left]] -= 1\n",
    "                left += 1\n",
    "            ans = max(ans,right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = left = cnts_t = cnts_f = 0\n",
    "        for right, c in enumerate(answerKey):\n",
    "            cnts_t += c == 'T'\n",
    "            cnts_f += c == 'F'\n",
    "            # 当前区间内的t和f的个数不能都大于k，我们只能变k次\n",
    "            while cnts_t > k and cnts_f > k:\n",
    "                # 超过最大变动次数了，当前指针的区间最左要向右移动\n",
    "                cnts_t -= answerKey[left] == 'T'\n",
    "                cnts_f -= answerKey[left] == 'F'\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(answerKey)\n",
    "        cntT = cntF = 0\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            if answerKey[right] == 'T':\n",
    "                cntT += 1\n",
    "            else:\n",
    "                cntF += 1\n",
    "            if cntT <= k or cntF <= k:\n",
    "                ans = right - left + 1\n",
    "            else:\n",
    "                if answerKey[left] == 'T':\n",
    "                    cntT -= 1\n",
    "                else:\n",
    "                    cntF -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(answerKey)\n",
    "        cntT = cntF = 0\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            if answerKey[right] == 'T':\n",
    "                cntT += 1\n",
    "            else:\n",
    "                cntF += 1\n",
    "            \n",
    "            if  cntF <= k or cntT <=k :\n",
    "                #ans = max(ans, right - left + 1)\n",
    "                ans = right - left + 1\n",
    "            else:\n",
    "                if answerKey[left] == 'T':\n",
    "                    cntT -= 1\n",
    "                else:\n",
    "                    cntF -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        T = F = left = 0\n",
    "        for c in answerKey:\n",
    "            if c == 'T':\n",
    "                T += 1\n",
    "            else:\n",
    "                F += 1\n",
    "\n",
    "            if T > k and F > k:\n",
    "                if answerKey[left] == 'T':\n",
    "                    T -= 1\n",
    "                else:\n",
    "                    F -= 1\n",
    "                left += 1\n",
    "        return len(answerKey) - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def getAns(s: str) -> int:\n",
    "            i, ans, cnt, l = 0, 0, Counter(), 0\n",
    "            for j, x in enumerate(answerKey):\n",
    "                cnt[x] += 1 if x == s else 0\n",
    "                l += 1\n",
    "                while cnt[x] > k:\n",
    "                    cnt[answerKey[i]] -= 1 if answerKey[i] == s else 0\n",
    "                    l -= 1\n",
    "                    if cnt[answerKey[i]] == 0:\n",
    "                        del cnt[answerKey[i]]\n",
    "                    i += 1\n",
    "                ans = max(ans, l)\n",
    "            return ans\n",
    "        return max(getAns('T'), getAns('F'))\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        l = r = 0\n",
    "        t = f = 0\n",
    "        while l <= r < len(answerKey):\n",
    "            if answerKey[r] == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "            if t <= k or f <= k:\n",
    "                if ans < r-l+1:\n",
    "                    ans = r - l + 1\n",
    "            else:\n",
    "                if answerKey[l] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1 \n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def max_consecutive_char(char: str) -> int:\n",
    "            ans = 0\n",
    "            left = 0\n",
    "            total = 0\n",
    "            for right in range(len(answerKey)):\n",
    "                total += answerKey[right] != char\n",
    "                while total > k:\n",
    "                    total -= answerKey[left] != char\n",
    "                    left += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "            return ans\n",
    "\n",
    "        return max(max_consecutive_char('T'), max_consecutive_char('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ret = left = cnt0 = cnt1 = 0\n",
    "        for right, x in enumerate(answerKey):\n",
    "            cnt0 += 1 - (x == 'T')\n",
    "            while cnt0 > k:\n",
    "                cnt0 -= 1 - (answerKey[left] == 'T')\n",
    "                left += 1\n",
    "            ret = max(ret, right - left + 1)\n",
    "        left = 0\n",
    "        for right, x in enumerate(answerKey):\n",
    "            cnt1 += 1 - (x == 'F')\n",
    "            while cnt1 > k:\n",
    "                cnt1 -= 1 - (answerKey[left] == 'F')\n",
    "                left += 1\n",
    "            ret = max(ret, right - left + 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        t, f = 0, 0\n",
    "        res = 0\n",
    "        while r < len(answerKey):\n",
    "            if answerKey[r] == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "            \n",
    "            while min(t, f) > k:\n",
    "                if answerKey[l] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1\n",
    "                l += 1\n",
    "            res = max(res, r-l+1)\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def f(a):\n",
    "            # 单调滑动窗口，a是要被替换的\n",
    "            cntB = left = 0\n",
    "            for c in answerKey:\n",
    "                if c == a:\n",
    "                    cntB += 1\n",
    "                if cntB > k:\n",
    "                    if answerKey[left] == a:\n",
    "                        cntB -= 1\n",
    "                    left += 1\n",
    "            return len(answerKey) - left\n",
    "        \n",
    "        return max(f('T'), f('F'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans, l, n, cnt, total = 0, 0, len(answerKey), Counter(), 0\n",
    "        for i in range(n):\n",
    "            while answerKey[i] == 'F' and cnt['F'] == k:\n",
    "                total -= 1\n",
    "                cnt[answerKey[l]] -= 1\n",
    "                l += 1\n",
    "            total += 1\n",
    "            cnt[answerKey[i]] += 1\n",
    "            ans = max(ans, total)\n",
    "        l, total, cnt = 0, 0, Counter()\n",
    "        for i in range(n):\n",
    "            while answerKey[i] == 'T' and cnt['T'] == k:\n",
    "                total -= 1\n",
    "                cnt[answerKey[l]] -= 1\n",
    "                l += 1\n",
    "            total += 1\n",
    "            cnt[answerKey[i]] += 1\n",
    "            ans = max(ans, total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        t = 0\n",
    "        f = 0\n",
    "        while l <= r < len(answerKey):\n",
    "            if answerKey[r] == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "            if min(t, f) <= k:\n",
    "                ans = max(ans, r-l+1)\n",
    "                r += 1\n",
    "            else:\n",
    "                if answerKey[l] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1 \n",
    "                l += 1\n",
    "                r += 1\n",
    "        return ans               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ret = left = cnt0 = cnt1 = 0\n",
    "        for right, x in enumerate(answerKey):\n",
    "            cnt0 += 1 - (x == 'T')\n",
    "            while cnt0 > k:\n",
    "                cnt0 -= 1 - (answerKey[left] == 'T')\n",
    "                left += 1\n",
    "            ret = max(ret, right - left + 1)\n",
    "        left = 0\n",
    "        for right, x in enumerate(answerKey):\n",
    "            cnt1 += 1 - (x == 'F')\n",
    "            while cnt1 > k:\n",
    "                cnt1 -= 1 - (answerKey[left] == 'F')\n",
    "                left += 1\n",
    "            ret = max(ret, right - left + 1)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def check(v):\n",
    "            ret = left = cnt0 = 0\n",
    "            for right, x in enumerate(answerKey):\n",
    "                cnt0 += 1 - (x == v)\n",
    "                while cnt0 > k:\n",
    "                    cnt0 -= 1 - (answerKey[left] == v)\n",
    "                    left += 1\n",
    "                ret = max(ret, right - left + 1)\n",
    "            return ret\n",
    "        return max(check('T'), check('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def find_ans(char):\n",
    "            n = len(answerKey)\n",
    "            left, count, ans = 0, 0, 0\n",
    "            for right in range(n):\n",
    "                if answerKey[right]!=char:\n",
    "                    count += 1\n",
    "                while count>k:\n",
    "                    if answerKey[left]!=char:\n",
    "                        count -= 1\n",
    "                    left += 1\n",
    "                ans = max(right-left+1, ans)\n",
    "            return ans\n",
    "        return max(find_ans('T'), find_ans('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def get_char(ch):\n",
    "            n = len(answerKey)\n",
    "            ans = 0\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            while i < n:\n",
    "                cnt += (answerKey[i] == ch)\n",
    "                while cnt > k:\n",
    "                    cnt -= (answerKey[j] == ch)\n",
    "                    j += 1\n",
    "                ans = max(ans, i - j + 1)\n",
    "                i += 1\n",
    "                \n",
    "            return ans \n",
    "        return max(get_char('T'), get_char('F'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        if not answerKey:\n",
    "            return 0\n",
    "        left,right = 0,0\n",
    "        res = 0\n",
    "        need = {}\n",
    "        while right < len(answerKey):\n",
    "            if answerKey[right] not in need:\n",
    "                need[answerKey[right]] = 1\n",
    "            else:\n",
    "                need[answerKey[right]] += 1\n",
    "            \n",
    "            while (right - left + 1) - max(need.values()) > k:\n",
    "                need[answerKey[left]] -= 1\n",
    "                left += 1\n",
    "            res = max(res,right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def get_ans(ch):\n",
    "\n",
    "            n =len(answerKey)\n",
    "            left = ans = 0\n",
    "            res = 0\n",
    "            for right,item in enumerate(answerKey):\n",
    "                if item == ch :\n",
    "                    ans +=1\n",
    "                while ans > k:\n",
    "                    if answerKey[left] == ch:\n",
    "                        ans -= 1\n",
    "                    left += 1\n",
    "                res =max(res,right-left+1)\n",
    "            return res\n",
    "        return max(get_ans('T'),get_ans('F'))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def find_maxl(ch,k):\n",
    "            sm=0\n",
    "            left,ans=0,0\n",
    "            for right in range(len(answerKey)):\n",
    "                sm+=answerKey[right]!=ch\n",
    "                if sm>k:                    \n",
    "                    sm-=answerKey[left]!=ch\n",
    "                    left+=1\n",
    "                ans= max(right-left+1,ans)\n",
    "            return ans\n",
    "        return max(find_maxl('T',k),find_maxl('F',k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "\n",
    "        n = len(answerKey)\n",
    "        def calc(t:str)->int:\n",
    "            l =r = 0\n",
    "            ans = 0\n",
    "            cnt = 0\n",
    "            while r<n:\n",
    "                cnt += 1 if answerKey[r]!=t else 0 \n",
    "                while cnt>k:\n",
    "                    cnt -= 1 if answerKey[l]!=t else 0\n",
    "                    l+=1\n",
    "\n",
    "                ans = max(ans,r-l+1)\n",
    "                r+=1\n",
    "            \n",
    "            ans = max(ans,r-l)\n",
    "            return ans\n",
    "        return max(calc('T'),calc('F'))\n",
    "               \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        t = 0\n",
    "        f = 0\n",
    "        while l <= r < len(answerKey):\n",
    "            if answerKey[r] == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "            if min(t, f) <= k:\n",
    "                if ans < r-l+1:\n",
    "                    ans = r - l + 1\n",
    "                r += 1\n",
    "            else:\n",
    "                if answerKey[l] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1 \n",
    "                l += 1\n",
    "                r += 1\n",
    "        return ans               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        num_T=0\n",
    "        num_F=0\n",
    "        ans,left=0,0\n",
    "        for right,ch in enumerate(answerKey):\n",
    "            if ch=='T':\n",
    "                num_T+=1\n",
    "            else:\n",
    "                num_F+=1\n",
    "            while (min(num_T,num_F)>k):#k无法转变滑窗内一样的选项，最小值都比k大\n",
    "                if answerKey[left]=='T':\n",
    "                    num_T-=1\n",
    "                else:\n",
    "                    num_F-=1\n",
    "                left+=1\n",
    "            ans=max(ans,right-left+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        t = 0\n",
    "        f = 0\n",
    "        while l <= r < len(answerKey):\n",
    "            if answerKey[r] == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "            if t <= k or f <= k:\n",
    "                if ans < r-l+1:\n",
    "                    ans = r - l + 1\n",
    "            else:\n",
    "                if answerKey[l] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1 \n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        # 两次循环， 一次改为t，一次改为f\n",
    "        \n",
    "        # 改为t\n",
    "        left = 0\n",
    "        cnt = k\n",
    "        mx_T = 0\n",
    "        for i, ch in enumerate(answerKey):\n",
    "            if ch == \"F\":\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                if answerKey[left] == \"F\":\n",
    "                    cnt += 1\n",
    "                left += 1\n",
    "            mx_T = max(mx_T, i-left+1)  \n",
    "                    \n",
    "        # 改为f\n",
    "        left = 0\n",
    "        cnt = k\n",
    "        mx_F = 0\n",
    "        for i, ch in enumerate(answerKey):\n",
    "            if ch == \"T\":\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                if answerKey[left] == \"T\":\n",
    "                    cnt += 1\n",
    "                left += 1\n",
    "            mx_F = max(mx_F, i-left+1)  \n",
    "        return max(mx_T, mx_F)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def f(a, b):\n",
    "            # 单调滑动窗口，b是要被替换的\n",
    "            cntB = left = 0\n",
    "            for c in answerKey:\n",
    "                if c == b:\n",
    "                    cntB += 1\n",
    "                if cntB > k:\n",
    "                    if answerKey[left] == b:\n",
    "                        cntB -= 1\n",
    "                    left += 1\n",
    "            return len(answerKey) - left\n",
    "        \n",
    "        return max(f('T', 'F'), f('F', 'T'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        left = 0\n",
    "        l = [0, 0]\n",
    "        for c in answerKey:\n",
    "            l[c == 'T'] += 1\n",
    "            if l[0] > k and l[1] > k:\n",
    "                l[answerKey[left] == 'T'] -= 1\n",
    "                left += 1\n",
    "        return len(answerKey) - left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(answerKey)\n",
    "        cntT = cntF = 0\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            if answerKey[right] == 'T':\n",
    "                cntT += 1\n",
    "            else:\n",
    "                cntF += 1\n",
    "            \n",
    "            if  cntF <= k or cntT <=k :\n",
    "                ans = max(ans, right - left + 1)\n",
    "            else:\n",
    "                if answerKey[left] == 'T':\n",
    "                    cntT -= 1\n",
    "                else:\n",
    "                    cntF -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def calc(c) -> int:\n",
    "            l = r = 0\n",
    "            n = len(answerKey)\n",
    "            cntF = 0\n",
    "            ans = 0\n",
    "            while r < n:\n",
    "                if answerKey[r] == c:\n",
    "                    cntF += 1\n",
    "                    while cntF > k:\n",
    "                        cntF -= answerKey[l] == c\n",
    "                        l += 1\n",
    "                r += 1\n",
    "                ans = max(ans, r - l)\n",
    "            if cntF <= k: ans = max(ans, r - l)\n",
    "            return ans\n",
    "        return max(calc('F'), calc('T'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        #等价于求一个包含 'F' 或者 'T' 的个数不超过 kkk 的最大长度窗口。\n",
    "        from collections import Counter\n",
    "        def get_ch(ch):\n",
    "            left, res = 0, 0\n",
    "            dic = Counter()\n",
    "            \n",
    "            for right, x in enumerate(answerKey):\n",
    "                dic[x] +=1\n",
    "                while x != ch and dic[x] >k:\n",
    "                    dic[answerKey[left]] -=1\n",
    "                    left+=1\n",
    "                res = max(res, right-left+1)\n",
    "            return res\n",
    "        return max(get_ch(\"T\"), get_ch(\"F\"))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        s = 0\n",
    "        # 1: T, 0: F\n",
    "        def idx(tf: str):\n",
    "            return 0 if tf == \"F\" else 1\n",
    "        cnt = [0] * 2\n",
    "        for e in range(len(answerKey)):\n",
    "            cnt[idx(answerKey[e])] += 1\n",
    "            maxIdx = 0 if cnt[0] > cnt[1] else 1\n",
    "            if e - s + 1 > cnt[maxIdx] + k:\n",
    "                cnt[idx(answerKey[s])] -= 1\n",
    "                s += 1\n",
    "        return len(answerKey) - s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        t = 0\n",
    "        f = 0\n",
    "        while l <= r < len(answerKey):\n",
    "            if answerKey[r] == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "            if min(t, f) <= k:\n",
    "                if ans < r-l+1:\n",
    "                    ans = r - l + 1\n",
    "            else:\n",
    "                if answerKey[l] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1 \n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(answerKey)\n",
    "        cntT = cntF = 0\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            if answerKey[right] == 'T':\n",
    "                cntT += 1\n",
    "            else:\n",
    "                cntF += 1\n",
    "            \n",
    "            if  cntF <= k or cntT <=k :\n",
    "                ans = right - left + 1\n",
    "                \n",
    "            else:\n",
    "                if answerKey[left] == 'T':\n",
    "                    cntT -= 1\n",
    "                else:\n",
    "                    cntF -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        res = 0\n",
    "        tmp = ['T', 'F']\n",
    "        for o in tmp:\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            while i < len(answerKey):\n",
    "                if answerKey[i] == o:\n",
    "                    cnt += 1\n",
    "                while i-j+1-cnt > k:\n",
    "                    if answerKey[j] == o:\n",
    "                        cnt -= 1\n",
    "                    j += 1\n",
    "                res = max(res, i-j+1)\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        d, l, res = Counter(), 0, 0\n",
    "        for r, c in enumerate(answerKey):\n",
    "            d[c] += 1\n",
    "            while len(d) == 2 and min(d.values()) > k:\n",
    "                d[answerKey[l]] -= 1\n",
    "                if d[answerKey[l]] == 0:\n",
    "                    d.pop(answerKey[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def f(a, x):\n",
    "            ans = l = 0\n",
    "            for r, c in enumerate(answerKey):\n",
    "                if c != a:\n",
    "                    x -= 1\n",
    "                while x < 0:\n",
    "                    if answerKey[l] != a:\n",
    "                        x += 1\n",
    "                    l += 1\n",
    "                ans = max(ans, r - l + 1)\n",
    "            return ans\n",
    "        return max(f('T', k), f('F', k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        res, left = 0, 0\n",
    "        t, f = 0, 0\n",
    "\n",
    "        for right, ch in enumerate(answerKey):\n",
    "            if ch == \"T\":\n",
    "                t += 1\n",
    "            else:\n",
    "                f += 1\n",
    "\n",
    "            while (t > k) and (f > k):\n",
    "                if answerKey[left] == \"T\":\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    f -= 1\n",
    "                left += 1\n",
    "            \n",
    "            res = max(res, t + f)\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answers: str, k: int) -> int:\n",
    "        res = l1 = l2 = t1 = t2 = 0\n",
    "        for r in range(len(answers)):\n",
    "            if answers[r] == 'F':\n",
    "                t1 += 1\n",
    "            else:\n",
    "                t2 += 1\n",
    "\n",
    "            while t1 > k:\n",
    "                t1 -= answers[l1] == 'F'\n",
    "                l1 += 1\n",
    "\n",
    "            while t2 > k:\n",
    "                t2 -= answers[l2] == 'T'\n",
    "                l2 += 1\n",
    "\n",
    "            res = max(res, r - l1 + 1, r - l2 + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        max_length = 0  # 用于存储最大连续段的长度\n",
    "        n = len(answerKey)\n",
    "        \n",
    "        # 检查 'T'\n",
    "        left = 0\n",
    "        count_T = 0  # 窗口内 'T' 的数量\n",
    "        for right in range(n):\n",
    "            if answerKey[right] == 'T':\n",
    "                count_T += 1\n",
    "            \n",
    "            # 如果窗口内 'T' 的数量超过 k，缩小窗口\n",
    "            while count_T > k:\n",
    "                if answerKey[left] == 'T':\n",
    "                    count_T -= 1\n",
    "                left += 1\n",
    "            \n",
    "            # 更新最大连续段的长度\n",
    "            max_length = max(max_length, right - left + 1)\n",
    "        \n",
    "        # 检查 'F'\n",
    "        left = 0\n",
    "        count_F = 0  # 窗口内 'F' 的数量\n",
    "        for right in range(n):\n",
    "            if answerKey[right] == 'F':\n",
    "                count_F += 1\n",
    "            \n",
    "            # 如果窗口内 'F' 的数量超过 k，缩小窗口\n",
    "            while count_F > k:\n",
    "                if answerKey[left] == 'F':\n",
    "                    count_F -= 1\n",
    "                left += 1\n",
    "            \n",
    "            # 更新最大连续段的长度\n",
    "            max_length = max(max_length, right - left + 1)\n",
    "        \n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        from collections import Counter\n",
    "        def get_ch(ch):\n",
    "            left, res = 0, 0\n",
    "            dic = Counter()\n",
    "            \n",
    "            for right, x in enumerate(answerKey):\n",
    "                dic[x] +=1\n",
    "                while x != ch and dic[x] >k:\n",
    "                    dic[answerKey[left]] -=1\n",
    "                    left+=1\n",
    "                res = max(res, right-left+1)\n",
    "            return res\n",
    "        return max(get_ch(\"T\"), get_ch(\"F\"))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        def correct(answerKey, k, toTrue):\n",
    "            n = len(answerKey)\n",
    "            left, right = 0, 0\n",
    "            currCnt, maxCnt = 0, 0\n",
    "            while right < n:\n",
    "                if toTrue == (answerKey[right] == \"F\"):\n",
    "                    currCnt += 1\n",
    "                    while currCnt > k:\n",
    "                        if toTrue == (answerKey[left] == \"F\"):\n",
    "                            currCnt -= 1\n",
    "                        left += 1\n",
    "                maxCnt = max(maxCnt, right - left + 1)\n",
    "                right += 1\n",
    "            return maxCnt\n",
    "        return max(correct(answerKey, k, True), correct(answerKey, k, False))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        x, y = 1, len(answerKey)\n",
    "        def valid(z):\n",
    "            t, f = 0, 0\n",
    "            for i in range(z):\n",
    "                if answerKey[i] == 'T':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "\n",
    "            for i in range(z-1, len(answerKey)):\n",
    "                if i >= z:\n",
    "                    if answerKey[i] == 'T':\n",
    "                        t += 1\n",
    "                    else:\n",
    "                        f += 1\n",
    "                    if answerKey[i-z] == 'T':\n",
    "                        t -= 1\n",
    "                    else:\n",
    "                        f -= 1\n",
    "                if min(t, f) <= k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        while x < y:\n",
    "            z = (x+y+1)//2\n",
    "            if valid(z):\n",
    "                x = z\n",
    "            else:\n",
    "                y = z-1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        l=0\n",
    "        r=0\n",
    "        q=[]\n",
    "        for x in answerKey:\n",
    "            if x=='T':\n",
    "                q.append(1)\n",
    "            else:\n",
    "                q.append(0)\n",
    "        n=len(q)\n",
    "        s=0\n",
    "        ans=0\n",
    "        while r<n:\n",
    "           s+=q[r]\n",
    "           while l<n and s>k:\n",
    "              if q[l]==1:\n",
    "                  s-=1\n",
    "              l+=1\n",
    "\n",
    "           ans=max(ans,r-l+1)\n",
    "           r+=1\n",
    "        for i in range(n):\n",
    "            if q[i]==1:\n",
    "                q[i]=0\n",
    "            else:\n",
    "                q[i]=1\n",
    "        r=0\n",
    "        l=0\n",
    "        s=0\n",
    "        while r<n:\n",
    "            s+=q[r]\n",
    "            while l<n and s>k:\n",
    "                 if q[l]==1:\n",
    "                     s-=1\n",
    "                 l+=1\n",
    "\n",
    "            ans=max(ans,r-l+1)\n",
    "            r+=1\n",
    "        return ans                         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        f_list = [i for i in range(len(answerKey)) if answerKey[i] == \"F\"]\n",
    "        f_list.append(len(answerKey))\n",
    "        if k >= len(f_list):\n",
    "            return len(answerKey)\n",
    "        res = f_list[k]\n",
    "        for i in range(k+1, len(f_list)):\n",
    "            res = max(res, f_list[i] - f_list[i-k-1] - 1)\n",
    "        t_list = [i for i in range(len(answerKey)) if answerKey[i] == \"T\"]\n",
    "        t_list.append(len(answerKey))\n",
    "        if k >= len(t_list):\n",
    "            return len(answerKey)\n",
    "        res = max(t_list[k], res)\n",
    "        for i in range(k+1, len(t_list)):\n",
    "            res = max(res, t_list[i] - t_list[i-k-1] - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        s = len(answerKey)\n",
    "        n = [[i.start() for i in re.finditer('T',answerKey)],[i.start() for i in re.finditer('F',answerKey)]]\n",
    "        if len(n[0]) <= k or len(n[1]) <= k:\n",
    "            return s\n",
    "        n[0].insert(0,-1)\n",
    "        n[0].append(s)\n",
    "        n[1].insert(0,-1)\n",
    "        n[1].append(s)\n",
    "        result = 0\n",
    "        for i in range(len(n[0])-k-1):\n",
    "            result = max(result,n[0][i+k+1]-n[0][i]-1)\n",
    "        for i in range(len(n[1])-k-1):\n",
    "            result = max(result,n[1][i+k+1]-n[1][i]-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        n = len(answerKey)\n",
    "        T_index = [-1]\n",
    "        F_index = [-1]\n",
    "        for i in range(n):\n",
    "            if answerKey[i]=='T':\n",
    "                T_index.append(i) \n",
    "            else:\n",
    "                F_index.append(i)\n",
    "        \n",
    "        T_index.append(n)\n",
    "        F_index.append(n)\n",
    "\n",
    "        if len(F_index)-2<k or len(T_index)-2<k:\n",
    "            return n\n",
    "        res = 0\n",
    "        for i in range(1, len(T_index)):\n",
    "            j = i+k-1\n",
    "            if j<len(T_index)-1:\n",
    "                res = max(res, T_index[j+1]-T_index[i-1]-1)\n",
    "\n",
    "        for i in range(1, len(F_index)):\n",
    "            j = i+k-1\n",
    "            if j<len(F_index)-1:\n",
    "                res = max(res, F_index[j+1]-F_index[i-1]-1)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        s = len(answerKey)\n",
    "        n = [[-1]+[i.start() for i in re.finditer('T',answerKey)]+[s],[-1]+[i.start() for i in re.finditer('F',answerKey)]+[s]]\n",
    "        if min(len(n[0]),len(n[1]))-2 <= k:\n",
    "            return s\n",
    "        result = 0\n",
    "        for i in range(len(n[0])-k-1):\n",
    "            result = max(result,n[0][i+k+1]-n[0][i]-1)\n",
    "        for i in range(len(n[1])-k-1):\n",
    "            result = max(result,n[1][i+k+1]-n[1][i]-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        n = [[i.start() for i in re.finditer('T',answerKey)],[i.start() for i in re.finditer('F',answerKey)]]\n",
    "        if len(n[0]) <= k or len(n[1]) <= k:\n",
    "            return len(answerKey)\n",
    "        n[0].insert(0,-1)\n",
    "        n[0].append(len(answerKey))\n",
    "        n[1].insert(0,-1)\n",
    "        n[1].append(len(answerKey))\n",
    "        result = 0\n",
    "        for i in range(len(n[0])-k-1):\n",
    "            result = max(result,n[0][i+k+1]-n[0][i]-1)\n",
    "        for i in range(len(n[1])-k-1):\n",
    "            result = max(result,n[1][i+k+1]-n[1][i]-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        n = len(answerKey)\n",
    "        ans = [0 if c=='F' else 1 for c in answerKey]\n",
    "\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i-1]+ans[i-1]\n",
    "        \n",
    "        l,r = 0,0\n",
    "        max_res = 0\n",
    "        # range_sum + k>= range_len\n",
    "        while r<n:\n",
    "            while r<n and pre[r+1]-pre[l]+k<(r-l+1):\n",
    "                l+=1\n",
    "            max_res = max(max_res, r-l+1)\n",
    "            r += 1\n",
    "        \n",
    "        l,r = 0,0\n",
    "        while r<n:\n",
    "            while r<n and k<pre[r+1]-pre[l]:\n",
    "                l+=1\n",
    "            max_res = max(max_res, r-l+1)\n",
    "            r+=1\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        ret = 0\n",
    "        for t in 'TF':\n",
    "            f = [0] * (n + 1)\n",
    "            for i in range(n):\n",
    "                f[i + 1] = f[i] + (s[i] == t)\n",
    "            for i in range(n):\n",
    "                l, r = 0, i\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if f[i + 1] - f[m] <= k:\n",
    "                        r = m - 1\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                ret = max(ret, i - l + 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        # 两次滑动窗口，分别算出最大连续T和最大连续F的数目\n",
    "        n = len(answerKey)\n",
    "        ans = [0 if c=='F' else 1 for c in answerKey]\n",
    "\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i-1]+ans[i-1]\n",
    "        \n",
    "        l,r = 0,0\n",
    "        max_res = 0\n",
    "        # range_sum + k>= range_len\n",
    "        while r<n:\n",
    "            while r<n and pre[r+1]-pre[l]+k<(r-l+1):\n",
    "                l+=1\n",
    "            max_res = max(max_res, r-l+1)\n",
    "            r += 1\n",
    "        \n",
    "        l,r = 0,0\n",
    "        while r<n:\n",
    "            while r<n and k<pre[r+1]-pre[l]:\n",
    "                l+=1\n",
    "            max_res = max(max_res, r-l+1)\n",
    "            r+=1\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "        s = len(answerKey)\n",
    "        n = [[-1]+[i.start() for i in re.finditer('T',answerKey)]+[s],[-1]+[i.start() for i in re.finditer('F',answerKey)]+[s]]\n",
    "        if len(n[0])-2 <= k or len(n[1])-2 <= k:\n",
    "            return s\n",
    "        result = 0\n",
    "        for i in range(len(n[0])-k-1):\n",
    "            result = max(result,n[0][i+k+1]-n[0][i]-1)\n",
    "        for i in range(len(n[1])-k-1):\n",
    "            result = max(result,n[1][i+k+1]-n[1][i]-1)\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
